Although the present invention may be directed toward any number of signal compression areas, to aid the reader in understanding the present invention, we refer to a single area by way of example. This example being the compression of data that adds texture to a digital image.
Conventional graphics systems such those as found in personal computers and home video game computers, use a frame buffer to store all the graphic data information that will be displayed on the computer screen. A graphics engine must “render” or draw graphics information into the frame buffer. Textures such as bumps, scratches, and surface features were not modeled by early graphics rendering engines. Rather, extremely smooth surfaces were constructed over a framework of graphics primitives such as polygons and vectors. Current graphics engines map textures onto these surfaces to replace artificially smooth surfaces with realistic detail. Examples of a texture of an object include the grass on a lawn, or the skin-tone variations and wrinkles on a human face.
A texture map is comprised of texels (texture elements) that are stored in texture memory. Texture memory is a scarce resource, so in order to efficiently use it, the digital signal representing the texture map is often compressed with a fixed compression ratio.
U.S. Pat. No. 5,822,452 discloses a method and system for “compressing and decompressing a texture image”. This method and various obvious improvements and modifications have been widely studied and adopted. The method is the following: a compression color space is selected either manually or using a neural network, each texel in the texture image is converted to an 8-bit value in the selected color space, and a decompression table is generated that represents the RGB values for each texel stored in the selected color space. When rendering a pixel representing an object with a texture, the texture image is mapped to the representation of the object, and one or more texels that are associated with each pixel are decompressed.
The inventors in U.S. Pat. No. 5,822,452 go to great lengths to describe their neural network algorithm for selecting the compression color space. In fact, this method is an ad hoc, heuristic, and sub-optimal example of a gradient descent method. Neural networks are frequently found to produce performance that may be superior to random guessing for poorly characterized and/or mathematically intractable optimization problems. The neural network as disclosed operates by iteratively modifying the choice of color space such that for each individual texel value, in turn, the distortion is lowered. However, lowering the distortion for a particular input may raise the distortion for the rest of the inputs leading to a net overall increase in distortion. In practice, more often than not, by using ad hoc techniques such as these, supplemented with user intervention to tune various optimization parameters, acceptable performance may be realized, but with much greater effort, both computational and human, than what may be possible with a principled approach.
Although the above referenced prior art patent deals specifically with the compression of color spaces, there is a more general need for a simple improved method of optimally compressing digital signals. In other words, an improvement to manual, neural network, and other ad hoc approaches. The present invention addresses this need.